package Sort;

/**
 * @author Liangyaoyun
 */
public class review {
    public void shellSort(int[] nums) {
        if (nums.length == 0 && nums == null) {
            return;
        }
        int tmp;
        int gap = nums.length / 2;
        while (gap >= 1) {
            //用于选定[gap，n-1]范围内每一个元素执行以gap为间隔的插入排序操作
            for (int i = gap; i < nums.length; i++) {
                //实现选定元素与前序下标取值间隔为gap的所有同组元素之间的比较和交换过程
                for (int j = i; j >= gap; j -= gap) {
                    if (nums[j] < nums[j - gap]) {
                        tmp = nums[j];
                        nums[j] = nums[j - gap];
                        nums[j - gap] = tmp;
                    }
                }
            }
            gap /= 2;
        }
    }


    public void quickSort(int[] nums, int start, int end) {
        if (end - start <= 0) {
            return;
        }
        int i = start;
        int j = end;
        while (i < j) {
            while (i < j && nums[j] >= nums[i]) {
                j--;
            }
            if (nums[i] > nums[j]) {
                int tmp = nums[j];
                nums[j] = nums[i];
                nums[i] = tmp;
            }
            while (i < j && nums[i] <= nums[j]) {
                i++;
            }
            //i从左向右走，如果nums[i]<nums[j],将两数交换
            if (i < j) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        int middle = i;
        quickSort(nums, start, middle - 1);
        quickSort(nums, middle + 1, end);
    }


    public void mergeSort(int[] nums) {
        int[] numsSort = new int[nums.length];
        mergeSortInner(nums, 0, nums.length - 1, numsSort);
    }

    public void mergeSortInner(int[] nums, int start, int end, int[] numsSort) {
        if (start == end) {
            return;
        }
        int middle = (end + start) / 2;
        int i = start;
        int j = middle + 1;
        int k = start;

        mergeSortInner(nums, start, middle, numsSort);
        mergeSortInner(nums, middle + 1, end, numsSort);

        while (i < middle && j < end) {
            if (nums[i] >= nums[j]) {
                numsSort[k] = nums[j];
                j++;
            } else {
                numsSort[k] = nums[i];
                i++;
            }
            k++;
        }
        while (i <= middle) {
            numsSort[k++] = nums[i++];
        }
        while (j <= end) {
            numsSort[k++] = nums[j++];
        }
        for (int l = start; l < end; l++) {
            nums[l] = numsSort[l];
        }
    }

    public void heapSort(int[] nums) {
        int tmp;
        for (int root = nums.length / 2 - 1; root >= 0; root--) {
            maxHeap(nums,root, nums.length-1);
        }

        //3.将堆顶出堆，然后再将堆结构整体调整为大根堆，循环往复，直到堆当中只剩余1个元素为止
        //end变量表示的是当前堆结构对应的数组中，最后一位元素的下标
        for (int end = nums.length-1; end >0 ; end--) {
            tmp=nums[0];
            nums[0]=nums[end];
            nums[end]=tmp;

            maxHeap(nums,0,end-1);
        }
    }
    public void maxHeap(int[] nums,int root,int end){
        int tmp;
        int lChild=2*root+1;
        int rChild=2*root+2;
        if (lChild>end){
            return;
        }
        int change=rChild<=end&&nums[rChild]>nums[lChild]?rChild:lChild;
        //3.1如果找到的孩子节点的取值大于父节点的取值，则将孩子与父节点进行交换
        if (nums[change]>nums[root]){
            tmp=nums[root];
            nums[root]=nums[change];
            nums[change]=tmp;
            //3.2交换之后的子堆堆顶可能失去大根堆特性，递归调整
            maxHeap(nums, change, end);
        }else {
            return;
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{6, 1, 0, 3, 9, 8, 4, 7, 5, 2};
        review review=new review();
        review.quickSort(nums,0, nums.length-1);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
    }
}
